package likou.offer;

import java.util.*;

/**
 * @Info: 机器人的运动范围
 * @Author: 唐小尊
 * @Date: 2020/8/1  13:28
 */
public class _13 {
    static int count = 0;
    static Map<Integer, List<Integer>> daan = new HashMap<Integer,List<Integer>>();
    static int ww[][] = new int[38][15];

    public static void main(String[] args) {
        System.out.println(movingCount2(38, 15, 9));

        Iterator it = daan.keySet().iterator();
        while (it.hasNext()) {
            int key = (Integer) it.next();
            List<Integer> value = (List<Integer>) daan.get(key);
            Collections.sort(value);
            System.out.println( key + "---"+ value);
        }


        System.out.println(movingCount(38, 15, 9));
    }

    public static int movingCount2(int m, int n, int k) {
        panduan(m, n, k, 0, 0, ww);
        return count;
    }

    public static void panduan(int m, int n, int k, int i, int j, int[][] ww) {
        ww[i][j] = -1;
        int nowCount = 0;
        int ic = i, jc = j;
        while (jc != 0) {
            nowCount += jc % 10;
            jc /= 10;
        }
        while (ic != 0) {
            nowCount += ic % 10;
            ic /= 10;
        }
        if (nowCount <= k) {
            if (!daan.containsKey(i)){
                List<Integer> integers = new ArrayList<>();
                integers.add(j);
                daan.put(i,integers);
            }else {
                List<Integer> integers = daan.get(i);
                integers.add(j);
                daan.put(i,integers);
            }
            count++;
            if (j + 1 < n && ww[i][j + 1] != -1) {
                panduan(m, n, k, i, j + 1, ww);
            }
            if (i + 1 < m && ww[i + 1][j] != -1) {
                panduan(m, n, k, i + 1, j, ww);
            }
            if (i > 0 && ww[i - 1][j] != -1) {
                panduan(m, n, k, i - 1, j, ww);
            }
            if (j > 0 && ww[i][j - 1] != -1) {
                panduan(m, n, k, i, j - 1, ww);
            }
        }
    }

    static boolean[][] visited;

    public static int movingCount(int m, int n, int k) {
        visited = new boolean[m][n];
        return dfs(0, 0, 0, 0, m, n, k);
    }

    public static int dfs(int i, int j, int si, int sj, int m, int n, int k) {
        if (i >= m || j >= n || k < si + sj || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj, m, n, k) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8, m, n, k);
    }
//
//
//    public int movingCount1(int m, int n, int k) {
//        boolean[][] visited = new boolean[m][n];
//        int res = 0;
//        Queue<int[]> queue= new LinkedList<int[]>();
//        queue.add(new int[] { 0, 0, 0, 0 });
//        while(queue.size() > 0) {
//            int[] x = queue.poll();
//            int i = x[0], j = x[1], si = x[2], sj = x[3];
//            if(i >= m || j >= n || k < si + sj || visited[i][j]) continue;
//            visited[i][j] = true;
//            res ++;
//            queue.add(new int[] { i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj });
//            queue.add(new int[] { i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8 });
//        }
//        return res;
//    }


}
